package november.sort;

import java.util.Arrays;

/**
 * @author huangxin
 * @date 2019/11/19-17:41
 */
public class RadixSort {
    public static void main(String[] args) {
        int[] arr = new int[8000000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * 800000);
        }
//        int[] arr = {2, 5, 6, 1, 123, 9, 1, 12, 7};
        long timeMillis1 = System.currentTimeMillis();

        radixSort2(arr);
        long timeMillis2 = System.currentTimeMillis();
        System.out.println(Arrays.toString(arr));
        System.out.println(timeMillis2 - timeMillis1);
    }

    /**
     * @param arr 排序的数组
     */
    public static void radixSort(int arr[]) {
        //获取最大值
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (max < arr[i]) {
                max = arr[i];
            }
        }
        //获取最大值长度
        int numLength = 0;
        while (max != 0) {
            numLength++;
            max /= 10;
        }

        //桶
        int[][] bucket = new int[10][arr.length + 1];

        int div = 1;
        //循环最大值的位数次
        for (int i = 0; i < numLength; i++) {
            //循环
            for (int j = 0; j < arr.length; j++) {
                //获取(个,十,白,千......)位数
                int index = (arr[j] / div) % 10;
                //增加有效个数
                bucket[index][0]++;
                //要插入的桶第一位的数用来存储有效个数
                int insertIndex = bucket[index][0];
                bucket[index][insertIndex] = arr[j];
            }

            int tempIndex = 0;
            //遍历桶
            for (int j = 0; j < bucket.length; j++) {
                for (int k = 1; k <= bucket[j][0]; k++) {//bucket[j][0]当前桶的有效个数
                    arr[tempIndex] = bucket[j][k];//取出
                    tempIndex++;
                }
                //清空有效个数
                bucket[j][0] = 0;
            }
            //乘10
            div *= 10;
        }
    }


    /**
     * @param arr 排序的数组
     */
    public static void radixSort2(int arr[]) {
        //获取最大值
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (max < arr[i]) {
                max = arr[i];
            }
        }
        //获取最大值长度
        int numLength = 0;
        while (max != 0) {
            numLength++;
            max /= 10;
        }

        int[][] bucket = new int[10][arr.length];
        int[] bucketCount = new int[10];

        int div = 1;
        //循环最大值的位数次
        for (int i = 0; i < numLength; i++) {
            //循环
            for (int j = 0; j < arr.length; j++) {
                //获取(个,十,白,千......)位数
                int index = (arr[j] / div) % 10;
                //获取该桶的有效个数
                int insertIndex = bucketCount[index];
                bucket[index][insertIndex] = arr[j];
                //增加有效个数
                bucketCount[index]++;
            }

            int tempIndex = 0;
            //遍历桶
            for (int j = 0; j < bucket.length; j++) {
                for (int k = 0; k < bucketCount[j]; k++) {//bucketCount[j]当前桶的有效个数
                    arr[tempIndex] = bucket[j][k];//取出桶中的数据赋值
                    tempIndex++;
                }
                //清空有效个数
                bucketCount[j] = 0;
            }
            //乘10
            div *= 10;
        }
    }
}
